package everydayone.minDistance;
/**
 * @Date 2020/04/06
 * @author 王光浩
 * @Thinking 使用DP思想,加上dp[i][j]表示，word1前i个字母转换为word2前j个字母所需要的最小次数，则可以
 * @         获取一个公式：dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+i和j所在字符是否相等。
 * @Analysis 时间复杂度O（n*m），空间复杂度O（1）
 */
public class MyMethodOne {
	public int minDistance(String word1, String word2) {
        int[][] dp=new int[word1.length()][word2.length()];
        if(word1.length()==0)return word2.length();
        if(word2.length()==0)return word1.length();
        //初始化信息
        for(int i=0;i<word1.length();i++)dp[i][0]=i;
        for(int i=0;i<word2.length();i++)dp[0][i]=i;
        //利用动态规划的公式进行计算
        for(int i=1;i<word1.length();i++)
        	for(int j=1;j<word2.length();j++) {
        		int min=Integer.MAX_VALUE;
        		if((dp[i][j-1]+1)<min)min=dp[i][j-1]+1;
        		if((dp[i-1][j]+1)<min)min=dp[i-1][j]+1;
        		int flag=(word1.charAt(i)==word2.charAt(j))?0:1;
        		if((dp[i-1][j-1]+flag)<min)min=dp[i-1][j-1];
        		dp[i][j]=min;
        	}
        return dp[word1.length()-1][word2.length()-1];
    }
}
